# 给出一个字符串 S，考虑其所有重复子串（S 的连续子串，出现两次或多次，可能会有重叠）。 
# 
#  返回任何具有最长可能长度的重复子串。（如果 S 不含重复子串，那么答案为 ""。） 
# 
#  
# 
#  示例 1： 
# 
#  输入："banana"
# 输出："ana"
#  
# 
#  示例 2： 
# 
#  输入："abcd"
# 输出：""
#  
# 
#  
# 
#  提示： 
# 
#  
#  2 <= S.length <= 10^5 
#  S 由小写英文字母组成。 
#  
#  Related Topics 哈希表 二分查找 
#  👍 73 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def longestDupSubstring(self, S: str) -> str:
        suffix = []
        s = ""
        for char in S[::-1]:
            s = char + s
            suffix.append(s)

        suffix.sort()

        res = ""
        for i in range(1, len(suffix)):

            j = k = 0
            while j < len(suffix[i - 1]) and j < len(suffix[i]) \
                    and suffix[i - 1][j] == suffix[i][k]:
                j += 1
                k += 1

            if k > len(res):
                res = suffix[i - 1][:k]

        print(res)


# leetcode submit region end(Prohibit modification and deletion)


Solution().longestDupSubstring("banana")
